package Easy;

// 28.实现strStr()
// 给定一个haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。
// 如果不存在，则返回 -1。
public class Solution28 {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        if (needle.length() > haystack.length())
            return -1;
        int i, j, index = -1;
        for (i = 0, j = 0; i < haystack.length() && j < needle.length(); i++) {
            if (haystack.charAt(i) == needle.charAt(j) && index == -1) {
                index = i;
                j++;
            } else if (haystack.charAt(i) == needle.charAt(j) && index != -1) {
                j++;
            } else {
                if (index != -1)
                    i=index;//这个字符串的当前位置不对了，就要回头找
                index = -1;
                j = 0;
            }
        }
        if(j==needle.length())
            return index;
        return -1;
    }
}
// 此题最优解法应采用滚动哈希，只需要O(L)的时间复杂度计算哈希值，L=neddle.length，
// 此方法最坏情况复杂度为O(N),N=haystack.length
// 我的解法最坏的情况下时间复杂度将由O(N)升至 O((N - L)L)